// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-05 15:30
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.GraphyTrain.UFS;

import org.junit.jupiter.api.Test;

@SuppressWarnings("AlibabaUndefineMagicConstant")
public class Solve {
    /**
     * 填充封闭图形，使用DFS踩点
     *
     * @param board
     */

    int[] X = {0, 0, 1, -1};
    int[] Y = {1, -1, 0, 0};
    int[][] Path;

    public void solve(char[][] board) {
        int n = board.length;
        int m = board[0].length;
        Path = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                char c = board[i][j];
                if (i == 0 || j == 0 || i == n - 1 || j == m - 1) {
                    if (board[i][j] == 'O' && Path[i][j] == 0) {
                        // 边界值点，而且边界值点为'o'
                        DFS(i, j, board);
                    }
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 'O' && Path[i][j] == 0) {
                    board[i][j] = 'X';
                }
            }
        }


    }

    private void DFS(int i, int j, char[][] board) {
        // 从边界点出发进行深度优先遍历（踩点）
        int n = board.length;
        int m = board[0].length;
        if (!(i >= 0 && i < n && j >= 0 && j < m)) {
            return;
        }
        Path[i][j] = 1;
        for (int k = 0; k < 4; k++) {
            int x = i + X[k];
            int y = j + Y[k];
            if (x >= 0 && x < n && y >= 0 && y < m && board[x][y] == 'O' && Path[x][y] == 0) {
                // 坐标在地图上
                DFS(x, y, board);
            }
        }
    }

    @Test
    public void shout() {
        //char[][] board = {{'O'}};
        char[][] board = {{'O', 'X', 'X', 'O', 'X'}, {'X', 'O', 'O', 'X', 'O'}, {'X', 'O', 'X', 'O', 'X'}, {'O', 'X', 'O', 'O', 'O'}, {'X', 'X', 'O', 'X', 'O'}};
        for (char[] chars : board) {
            System.out.println();
            for (char aChar : chars) {
                System.out.print(aChar + "\t");
            }
        }
        System.out.print("\n++++++++++++After++++++++++++");
        solve(board);
        for (char[] chars : board) {
            System.out.println();
            for (char aChar : chars) {
                System.out.print(aChar + "\t");
            }
        }
    }


}



